package sword_offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Synhard
 * @version 1.0
 * @class Code64
 * @description 剑指 Offer 57 - II. 和为s的连续正数序列
 * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
 *
 * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：target = 9
 * 输出：[[2,3,4],[4,5]]
 * 示例 2：
 *
 * 输入：target = 15
 * 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
 *  
 *
 * 限制：
 *
 * 1 <= target <= 10^5
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-16 7:55
 */
public class Code64 {
    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(findContinuousSequence(15)));
    }

    public static int[][] findContinuousSequence(int target) {
        List<List<Integer>> res = new ArrayList<>();
        int right = (target >> 1) + 1, left = right - 1;
        while (right > 0) {
            while (left > 0) {
                List<Integer> tmp = new ArrayList<>();
                int sum = (left + right) * (right - left + 1) / 2;
                if (sum == target) {
                    for (int i = left; i <= right; i++) {
                        tmp.add(i);
                    }
                    res.add(tmp);
                    break;
                }
                if (sum > target) {
                    break;
                }
                left--;
            }
            right--;
            left = right - 1;
        }
        int[][] ret = new int[res.size()][];
        int retIndex = 0;
        for (int i = res.size() - 1; i > -1; i--) {
            List<Integer> list = res.get(i);
            int[] array = new int[list.size()];
            int arrayIndex = 0;
            for (int num : list) {
                array[arrayIndex++] = num;
            }
            ret[retIndex++] = array;
        }
        return ret;
    }
}
/*
双指针
 */